package com.dhu.graph.commonGrpaph;

import com.dhu.graph.basic.GraphImpls.Graph;

/**
 * 基于深度优先搜索查找图中的连通分量
 */
public class CC {
    private boolean[] marked;
    private int[] id;   //连通分量的id
    private int count;  //连通分量数-1

    public CC(Graph G){
        marked = new boolean[G.getVertexes()];
        id = new int [G.getVertexes()];
        for(int i = 0; i < G.getVertexes(); i++){
            if(isMarked(i)){
                dsf(G,i);        //利用深度优先搜索找到连通的顶点们。
                count ++;       //在这里每一次dsf开始都是从一个独立分量的起点开始
            }
        }
    }

    private void dsf(Graph G, int s){
        marked[s] = true;
        id[s] = count;      //标记s并未s的id 赋值
        for (Integer w : G.adj(s)) {
            if(isMarked(s)){
                dsf(G, w);
            }
        }
    }
    private boolean isMarked(int v){
        return !marked[v];
    }
    public int count(){
        return count ++;
    }

    public boolean isConnect(int x, int y){
        return id[x] == id[y];      //同union-find
    }
}
